#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
int len,dp[MAXN];

int find(int x){
    int left=1,right=len,mid;
    while(left<=right){
        mid = (left+right)/2;
        if(x>dp[mid])
            left = mid + 1;
        else if(x<dp[mid])
            right  = mid -1;
        else
            return mid;
    }
    return left;
}

int main(){
    int i,j,n=7,a[MAXN] = {1,7,3,5,9,4,8};
    //input
    len = 1,dp[1] = a[0];
    for(i=1;i<n;i++){
        j = find(a[i]);
        dp[j] = a[i];
        if(j>len)
            len = j;
    }
    for(i=1;i<=len;i++)
        printf("%d ",dp[i]);
    printf("\n%d\n",len);
}
